London Maths Outreach course: Effective Methods in Algebra

17:00 PM to 19:00 PM on Wednesdays, 19 March, 26 March, 2 April, 2025.

Instructor: Abhiram Natarajan (abhiram.natarajan[light at the end of the tunnel]warwick.ac.uk)

This course is run as part of the London Maths Outreach organised in collaboration with University College London, London School of Geometry and Number Theory, and Imperial College.


Course Description: 'Algebra' commonly refers to Elementary Algebra, which involves arithmetic with numerical values and variables, or Abstract Algebra, which is algebra in full generality applicable to nearly any mathematical domain. To say that algebra is fundamental to mathematics would be an understatement — it is nearly impossible to separate algebra from any mathematical activity. In this course, we will explore algorithmic methods for solving problems in both linear and nonlinear algebra. We will examine how algorithms for fundamental tasks, such as solving systems of linear equations/polynomials, connect to diverse areas like geometry, topology, computational complexity, combinatorics, and probability. Students can expect to have a fun ride as they witness how simple algebraic procedures give rise to deep and unexpected connections across seemingly unrelated fields of mathematics.


Prerequisites: I will try to make the course as self-contained as possible. Students of all backgrounds are welcome. Basic high-school level mathematical maturity will be assumed.

Before each lecture, I will mention (well in advance) what you need to be familiar with to follow the lecture. I will also post resources which will help you gain familiarity. Not only that, I am most happy to engage with you outside class to discuss those concepts and help you. During the actual class, I might give brief introductions to those concepts, but can make no promise about it. It would be best if you are prepared that I will assume familiarity with those concepts.


Presentation schedule:
Date Prerequisites Topics Notes
Week 1 (Mar 19) basic algebra, dealing with variables, solving a small system of linear equations algorithms, solving system of linear equations using Gaussian elimination, geometric interpretation of Gaussian elimination, determinant of a matrix, geometric meaning of determinant, computing the determinant using Gaussian elimination, permanent of a matrix, complexity of computing the permanent notes
Week 2 (Mar 26) polynomials Grobner Basis: computation of S-polynomials, Buchberger's algorithm; applications of Grobner bases: solvability of polynomial systems, polynomial division, de Rham Cohomology and Betti numbers, zero-knowledge proofs notes
Week 3 (Apr 2) probability complexity of Grobner basis computation, asymptotic analysis, power of randomness - Buffon needle experiment to estimate pi, randomized quick sort, randomized algorithm for testing equalilty of polynomial expressions, applications in cryptography - Shamir Secret Sharing and Verifiable Secret Sharing, etc., PCP (Probabilistically Checkable Proofs) Theorem notes


Expectations: Active class participation is most encouraged. To get the maximum out of the course, do the assignments diligently.


Textbooks/Sources: There will be no singular reference for this class. I plan on using a myriad of sources. Below is list that will be updated as we go along.

Acknowledgements: Copied webpage template from Jarod Alper's course on algebraic complexity theory.